package two.chapter_2.c2_3;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import two.chapter_1.c1_1.Printer;
import two.chapter_2.c2_1.Sortable;

/**
 * 快速排序
 * 分治思想，将待排序数组按数组中某一个数为标准分成左右两部分，左边的数都小于这个标准值，右边的数都大于这个标准数
 * 当这左右两边的数排序完成时，整个数组也就排序完成了。
 *
 * @param <Item>
 */
public class QuickSort<Item extends Comparable<Item>> extends Sortable<Item> {


    @Override
    public void sort(Item[] items) {
        StdRandom.shuffle(items);
        sort(items, 0, items.length - 1);

    }

    private void sort(Item[] items, int lo, int hi) {

        if (lo >= hi) {
            return;
        }

        int j = partition(items, lo, hi);//切分函数
       // StdOut.println("lo:"+lo+" j："+j+"  hi:"+hi);
        sort(items, lo, j - 1);
        sort(items, j + 1, hi);
    }

    /**
     * 切分函数  返回值为选定键的index
     * 该键的左边都小于等于该建，该键的右边都大于等于该键
     * <p>
     * 设items[lo]为选定的切分键
     * 数组最左边i指针，数组最右边j指针
     * <p>
     * i指针从左向右扫描，
     * i指针扫描到的值大于切分键时，
     * j指针从右向左扫描，扫描到小于切分键时和i指针的值交换。
     * 直到i=j,结束
     *
     * @param items
     * @param lo
     * @param hi
     * @return
     */
    private int partition(Item[] items, int lo, int hi) {

        Item key = items[lo];
        int i = lo;
        int j = hi;
        while (i<=j){
            if (less(key,items[i])){
                if (less(items[j],key)){
                    exch(i,j,items);
                    //Printer.printArray(items);
                    i++;
                    j--;
                }else {
                    j--;
                }
            }else {
                i++;
            }
        }
        exch(lo, j, items);
        /*
         Item key = items[lo];
        int i = lo;
        int j = hi+1;
        while (true) {
            while (less(items[++i], key)) {
                if (i == hi) {
                    break;
                }
            }
            while (less(key, items[--j])) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            exch(i, j, items);
        }
        exch(lo, j, items);*/
        return j;
    }
}
